/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
/*
	This file defines iterator that use in stl.
	The "struct iterator" is the base defining basic type in iterator class.
	The "struct iterator_traits" traits features of an class-iterator or a nativ pointer.
		These features include the types "iterator", "const_iterator","reverse_iterator"
		and "const_reverse_iterator"

*/
#ifndef __STD_ITERATOR_H_VERSION_KL__
#define __STD_ITERATOR_H_VERSION_KL__
#define _KL_USE_ITERATOR_TRAITS_
#define _KL_USE_ITERATOR_HELPER_
#define _KL_USE_ITERATOR_FUNCTION_
#define _KL_USE_RANDOM_INT_
#define _KL_USE_CONST_ITERATOR_
#define _KL_USE_REVERSE_ITERATOR_
#define STD_ITERATOR_DEFINE(inner_iterator) \
	typedef KL::iterator_traits<inner_iterator> _itraits; \
	typedef typename _itraits::iterator iterator; \
	typedef typename _itraits::const_iterator const_iterator; \
	typedef typename _itraits::reverse_iterator reverse_iterator; \
	typedef typename _itraits::const_reverse_iterator const_reverse_iterator;

#include "utility.h"

KL_BEGIN
#ifdef _KL_USE_ITERATOR_TRAITS_
// CLASS iterator base {
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag, output_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
// CLASS iterator base }
// CLASS iterator {
template <class Tag, class Type>
struct iterator
{
	KL_TYPE_DEFINE(Type);
	typedef Tag iterator_category;
};
// CLASS iterator }
// CLASS iterator_traits {
template<typename Iterator>
struct _iterator_;
template<typename Iterator>
struct _const_iterator_;
template<typename Iterator>
struct _reverse_iterator_;
template<typename Iterator>
struct _const_reverse_iterator_;
template<class Iterator>
struct iterator_traits
{	
	KL_TYPE_DEFINE(typename Iterator::value_type);
	typedef typename Iterator::iterator_category iterator_category;
	typedef KL::_iterator_<Iterator> iterator;
	typedef KL::_const_iterator_<Iterator> const_iterator;
	typedef KL::_reverse_iterator_<Iterator> reverse_iterator;
	typedef KL::_const_reverse_iterator_<Iterator> const_reverse_iterator;
};
template<typename Type>
struct iterator_traits <Type *> 
{
	KL_TYPE_DEFINE(Type);
	typedef random_access_iterator_tag iterator_category;
	typedef Type * iterator;
	typedef const Type * const_iterator;
	typedef KL::_reverse_iterator_<Type *> reverse_iterator;
	typedef KL::_const_reverse_iterator_<Type *> const_reverse_iterator;
};
template<typename Type>
struct iterator_traits <Type const *> 
{
	KL_TYPE_DEFINE(Type);
	typedef random_access_iterator_tag iterator_category;
	typedef Type * iterator;
	typedef const Type * const_iterator;
	typedef KL::_reverse_iterator_<Type *> reverse_iterator;
	typedef KL::_const_reverse_iterator_<Type *> const_reverse_iterator;
};
// CLASS iterator_traits }
#endif //_KL_USE_ITERATOR_TRAITS_
#ifdef _KL_USE_CONST_ITERATOR_
// CLASS _iterator_ {
template<typename Iterator>
struct _iterator_ 
	: public KL::iterator<
		typename iterator_traits<Iterator>::iterator_category,
		typename iterator_traits<Iterator>::value_type
	>
{
	KL_TYPE_DEFINE(typename iterator_traits<Iterator>::value_type);
	
	Iterator _iter;
	_iterator_()
	{
	}
	explicit _iterator_(Iterator const &my)
		: _iter(my)
	{
	}
	operator Iterator()
	{
		return _iter;
	}
	operator Iterator() const
	{
		return _iter;
	}
	reference operator *()
	{
		return *_iter;
	}
	pointer operator ->()
	{
		return &*_iter;
	}
	_iterator_ & operator = (_iterator_ const &o)
	{
		_iter = o._iter;
		return *this;
	}
	_iterator_ & operator ++ ()
	{
		++_iter;
		return *this;
	}
	_iterator_ & operator -- ()
	{
		--_iter;
		return *this;
	}
	_iterator_ operator ++ (int)
	{
		_iterator_ temp = *this;
		++_iter;
		return temp;
	}
	_iterator_ operator -- (int)
	{
		_iterator_ temp = *this;
		--_iter;
		return temp;
	}
	_iterator_ & operator -= (diff_type num)
	{
		_iter -= num;
		return *this;
	}
	_iterator_ & operator += (diff_type num)
	{
		_iter += num;
		return *this;
	}
	_iterator_ operator - (diff_type num) const
	{
		return _iterator_(_iter - num);
	}
	_iterator_ operator + (diff_type num) const
	{
		return _iterator_(_iter + num);
	}
	template<typename Type>
	diff_type operator - (_iterator_<Type> const &o) const
	{
		return _iter - o._iter;
	}
	bool operator < (_iterator_ const &o) const
	{
		return _iter < o._iter;
	}	
	bool operator == (_iterator_ const &o) const
	{
		return _iter == o._iter;
	}
};
// CLASS _iterator_ }
// CLASS _const_iterator_ {
template<typename Iterator>
struct _const_iterator_ 
	: KL::iterator<typename iterator_traits<Iterator>::iterator_category,
	typename iterator_traits<Iterator>::value_type>
{
	KL_TYPE_DEFINE(typename iterator_traits<Iterator>::value_type);
	Iterator _iter;
	_const_iterator_()
	{}
	explicit _const_iterator_(Iterator const &base)
		: _iter(base)
	{
	}
	_const_iterator_(_iterator_<Iterator> const &iter)
		: _iter(iter._iter)
	{
	}	
	operator Iterator()
	{
		return _iter;
	}
	operator Iterator() const
	{
		return _iter;
	}
	template<typename Type>
	_const_iterator_(_const_iterator_<Type> const &o)
		: _iter(o._iter)
	{
	}	
	template<typename Type>
	_const_iterator_ & operator = (_const_iterator_<Type> const &o)
	{
		_iter = o._iter;
		return *this;
	}
	_const_iterator_ & operator ++ ()
	{
		++_iter;
		return *this;
	}
	_const_iterator_ & operator -- ()
	{
		--_iter;
		return *this;
	}
	_const_iterator_ operator ++ (int)
	{
		_const_iterator_ temp = *this;
		++_iter;
		return temp;
	}
	_const_iterator_ operator -- (int)
	{
		_const_iterator_ temp = *this;
		--_iter;
		return temp;
	}
	const_reference operator *()
	{
		return *_iter;
	}
	const_pointer operator ->()
	{
		return &*_iter;
	}
	_const_iterator_ & operator -= (diff_type num)
	{
		_iter -= num;
		return *this;
	}
	_const_iterator_ & operator += (diff_type num)
	{
		_iter += num;
		return *this;
	}
	_const_iterator_ operator - (diff_type num) const
	{
		return _const_iterator_(_iter - num);
	}
	_const_iterator_ operator + (diff_type num) const
	{
		return _const_iterator_(_iter + num);
	}
	template<typename Type>
	diff_type operator - (_const_iterator_<Type> const &o) const
	{
		return _iter - o._iter;
	}
	bool operator < (_const_iterator_ const &o) const
	{
		return _iter < o._iter;
	}	
	bool operator == (_const_iterator_ const &o) const
	{
		return _iter == o._iter;
	}
};
// CLASS _const_iterator_ }
// SPECIALIZED CLASS iterator_traits (for _iterator_, _const_iterator_) {
template<typename Type>
struct iterator_traits<KL::_const_iterator_<Type>>
	: iterator_traits<Type>
{
};
template<typename Type>
struct iterator_traits<KL::_iterator_<Type>>
	: iterator_traits<Type>
{
};
// SPECIALIZED CLASS iterator_traits (for _iterator_, _const_iterator_) }
#endif // _KL_USE_CONST_ITERATOR_
#ifdef _KL_USE_REVERSE_ITERATOR_
// CLASS _reverse_iterator_ {
template<typename Iterator>
struct _reverse_iterator_
	: KL::iterator<typename iterator_traits<Iterator>::iterator_category,
	typename iterator_traits<Iterator>::value_type>
{
	KL_TYPE_DEFINE(typename iterator_traits<Iterator>::value_type);
	Iterator _iter;
	_reverse_iterator_()
	{}
	explicit _reverse_iterator_(Iterator const &base)
		: _iter(base)
	{
	}
	template<typename Type>
	_reverse_iterator_(_reverse_iterator_<Type> const &o)
		: _iter(o._iter)
	{
	}
	template<typename Type>
	_reverse_iterator_ &operator = (_reverse_iterator_<Type> const &o)
	{
		_iter = o._iter;
		return *this;
	}
	reference operator *()
	{
		return *_iter;
	}
	pointer operator ->()
	{
		return &*_iter;
	}
	_reverse_iterator_ & operator ++ ()
	{
		--_iter;
		return *this;
	}
	_reverse_iterator_ & operator -- ()
	{
		++_iter;
		return *this;
	}
	_reverse_iterator_ operator ++ (int)
	{
		_reverse_iterator_ temp = *this;
		--_iter;
		return temp;
	}
	_reverse_iterator_ operator -- (int)
	{
		_reverse_iterator_ temp = *this;
		++_iter;
		return temp;
	}
	_reverse_iterator_ & operator -= (diff_type num)
	{	// only for random_access_iterator
		_iter += num;
		return *this;
	}
	_reverse_iterator_ & operator += (diff_type num)
	{	// only for random_access_iterator
		_iter -= num;
		return *this;
	}
	_reverse_iterator_ operator - (diff_type num) const
	{	// only for random_access_iterator
		return _reverse_iterator_(_iter + num);
	}
	_reverse_iterator_ operator + (diff_type num) const
	{	// only for random_access_iterator
		return _reverse_iterator_(_iter - num);
	}
	template<typename Type>
	diff_type operator - (_reverse_iterator_<Type> const &o) const
	{	// only for random_access_iterator
		return o._iter - _iter;
	}
	bool operator < (_reverse_iterator_ const &o) const
	{	// only for random_access_iterator
		return _iter < o._iter;
	}	
	bool operator == (_reverse_iterator_ const &o) const
	{
		return _iter == o._iter;
	}
};
// CLASS _reverse_iterator_ }
// CLASS _const_reverse_iterator_ {
template<typename Iterator>
struct _const_reverse_iterator_
	: KL::iterator<typename iterator_traits<Iterator>::iterator_category,
	typename iterator_traits<Iterator>::value_type>
{
	KL_TYPE_DEFINE(typename iterator_traits<Iterator>::value_type);

	Iterator _iter;
	_const_reverse_iterator_()
	{}
	explicit _const_reverse_iterator_(Iterator const &base)
		: _iter(base)
	{
	}
	_const_reverse_iterator_(_reverse_iterator_<Iterator> const &iter)
		: _iter(iter._iter)
	{
	}
	template<typename Type>
	_const_reverse_iterator_(_const_reverse_iterator_<Type> const &o)
		: _iter(o._iter)
	{
	}	
	template<typename Type>
	_const_reverse_iterator_ & operator = (_const_reverse_iterator_<Type> const &o)
	{
		_iter = o._iter;
		return *this;
	}
	_const_reverse_iterator_ & operator ++ ()
	{
		--_iter;
		return *this;
	}
	_const_reverse_iterator_ & operator -- ()
	{
		++_iter;
		return *this;
	}
	_const_reverse_iterator_ operator ++ (int)
	{
		_const_reverse_iterator_ temp = *this;
		--_iter;
		return temp;
	}
	_const_reverse_iterator_ operator -- (int)
	{
		_const_reverse_iterator_ temp = *this;
		++_iter;
		return temp;
	}
	const_reference operator *()
	{
		return *_iter;
	}
	const_pointer operator ->()
	{
		return &*_iter;
	}
	_const_reverse_iterator_ & operator -= (diff_type num)
	{
		_iter += num;
		return *this;
	}
	_const_reverse_iterator_ & operator += (diff_type num)
	{
		_iter -= num;
		return *this;
	}
	_const_reverse_iterator_ operator - (diff_type num) const
	{
		return _const_reverse_iterator_(_iter + num);
	}
	_const_reverse_iterator_ operator + (diff_type num) const
	{
		return _const_reverse_iterator_(_iter - num);
	}
	template<typename Type>
	diff_type operator - (_const_reverse_iterator_<Type> const &o) const
	{
		return o._iter - _iter;
	}
	bool operator < (_const_reverse_iterator_ const &o) const
	{
		return _iter < o._iter;
	}	
	bool operator == (_const_reverse_iterator_ const &o) const
	{
		return _iter == o._iter;
	}
};
// CLASS _const_reverse_iterator_ }
// SPECIALIZED CLASS iterator_traits for(_reverse_iterator_, _const_reverse_iterator_) {
template<typename Type>
struct iterator_traits<KL::_reverse_iterator_<Type>>
	: iterator_traits<Type>
{	
	typedef typename iterator_traits<Type>::iterator reverse_iterator;
	typedef typename iterator_traits<Type>::reverse_iterator iterator;
	typedef typename iterator_traits<Type>::const_iterator const_reverse_iterator;
	typedef typename iterator_traits<Type>::const_reverse_iterator const_iterator;
};
template<typename Type>
struct iterator_traits<KL::_const_reverse_iterator_<Type>>
	: iterator_traits<Type>
{
	typedef typename iterator_traits<Type>::iterator reverse_iterator;
	typedef typename iterator_traits<Type>::reverse_iterator iterator;
	typedef typename iterator_traits<Type>::const_iterator const_reverse_iterator;
	typedef typename iterator_traits<Type>::const_reverse_iterator const_iterator;
};
// SPECIALIZED CLASS iterator_traits for(_reverse_iterator_, _const_reverse_iterator_) }
#endif //_KL_USE_REVERSE_ITERATOR_

#ifdef _KL_USE_ITERATOR_HELPER_
// CLASS _iterator_helper_ {
template<class Iterator, class Tag = typename iterator_traits<Iterator>::iterator_category>
struct _iterator_helper_ : _iterator_helper_<Iterator, bidirectional_iterator_tag>
{
};
template<class Iterator>
struct _iterator_helper_<Iterator, input_iterator_tag>
{	
	KL_TYPE_DEFINE(typename iterator_traits<Iterator>::value_type);
	typedef Iterator iterator;
	static inline void advance(iterator & iter, size_type num)
	{
		while(num--) ++iter;
	}
	static inline size_type distance(iterator first, iterator last) 
	{
		size_type dist = 0;
		for(;first != last; ++first, ++dist)
			ASSERT_REPAIR(dist < ~(size_type)0, return size_type(0));
		return dist;
	}
	static inline iterator 
		forward(iterator iter, size_type num)
	{
		while(num--) ++iter;
		return iter;
	}
};
template<class Iterator>
struct _iterator_helper_<Iterator, output_iterator_tag> 
	: public _iterator_helper_<Iterator, input_iterator_tag>
{
};
template<class Iterator>
struct _iterator_helper_<Iterator, forward_iterator_tag> 
	: public _iterator_helper_<Iterator, input_iterator_tag>
{
};
template<class Iterator>
struct _iterator_helper_<Iterator, bidirectional_iterator_tag>
	: public _iterator_helper_<Iterator, forward_iterator_tag> 
{
	KL_TYPE_DEFINE(typename iterator_traits<Iterator>::value_type);
	typedef Iterator iterator;

	static inline void advance(iterator &iter, size_type num)
	{
		while(num--) ++iter;
	}
	static inline void retreat(iterator &iter, size_type num)
	{
		while(num--) --iter;
	}
	static inline iterator backward(iterator iter, size_type num)
	{
		while(num--) --iter;
		return iter;
	}
};
template<class Iterator>
struct _iterator_helper_<Iterator, random_access_iterator_tag> 
{
	KL_TYPE_DEFINE(typename iterator_traits<Iterator>::value_type);
	typedef Iterator iterator;
	static inline void advance(iterator & iter, size_type num)
	{
		iter += num;
	}
	static inline void retreat(iterator &iter, size_type num)
	{
		iter -= num;
	}
	static inline size_type distance(iterator const &first, iterator const &last) 
	{
		ASSERT_REPAIR(!(last < first), return size_type(0));
		return last - first;
	}	
	static inline iterator 
		forward(iterator iter, size_type num)
	{
		return iter + num;
	}
	static inline iterator 
		backward(iterator iter, size_type num)
	{
		return iter - num;
	}
};
// CLASS _iterator_helper_ }
#endif // _KL_USE_ITERATOR_HELPER_
#ifdef _KL_USE_ITERATOR_FUNCTION_
// FUNCTION advance FUNCTION distance {
template<typename Iterator>
inline void advance(Iterator & iter, size_t num)
{
	_iterator_helper_<Iterator>::advance(iter, num);
}
template<typename Iterator>
inline size_t distance(Iterator const &first, Iterator const &last)
{
	return _iterator_helper_<Iterator>::distance(first, last);
}
template<typename Iterator>
inline void retreat(Iterator & iter, size_t num)
{
	_iterator_helper_<Iterator>::retreat(iter, num);
}
template<typename Iterator>
inline Iterator forward(Iterator iter, size_t num)
{
	return _iterator_helper_<Iterator>::forward(iter, num);
}
template<typename Iterator>
inline Iterator backward(Iterator iter, size_t num)
{
	return _iterator_helper_<Iterator>::backward(iter, num);
}
// FUNCTION advance FUNCTION distance }
// FUNCTION iterator_category FUNCTION value_type {
template<class Iterator>
inline typename iterator_traits<Iterator>::iterator_category* iterator_category(const Iterator &)
{
	return static_cast<typename iterator_traits<Iterator>::iterator_category*>(0);
}
template<class Iterator>
inline typename iterator_traits<Iterator>::value_type* value_type (const Iterator &)
{
	return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}
// FUNCTION iterator_category FUNCTION value_type }
#endif //_KL_USE_ITERATOR_FUNCTION_

#ifdef _KL_USE_RANDOM_INT_
// CLASS _random_integer_ {
template<typename Type = int, unsigned Max = 0xffffffff, typename TAG = KL::input_iterator_tag>
class _random_integer_ : public KL::iterator<TAG, Type>
{
public:
	KL_TYPE_DEFINE(Type);

protected:
	diff_type _n;
public:
	_random_integer_(diff_type n)
		: _n(n)
	{
	}
	Type operator * ()
	{
		return (Type)(rand() % Max);
	}
	_random_integer_ &operator ++()
	{
		++_n;
		return *this;
	}
	_random_integer_ &operator --()
	{
		++_n;
		return *this;
	}
	_random_integer_ operator ++(int)
	{
		return _n++;
	}
	_random_integer_ operator --(int)
	{
		return _n--;
	}
	bool operator == (_random_integer_ const &o)
	{
		return o._n == _n;
	}
	bool operator != (_random_integer_ const &o)
	{
		return o._n != _n;
	}
	void swap(_random_integer_ &o)
	{
		swap(_n, o._n);
	}
};
// CLASS _random_integer_ }
#endif // _KL_USE_RANDOM_INT_
KL_END

#endif // __STD_ITERATOR_H_VERSION_KL__
